package com.leetcode.offer03;

/**
 * 给定长度为n的数组nums，并且里面的值范围在0~n-1
 * 数组内的值可以重复
 * 0<=n<=1000
 * 要求计算出nums数组中任一重复数字
 *
 * 重点考察：原地排序算法
 * 如果 i != nums[i] 就进行交换
 * 如果 i == nums[i] i++
 * 重复条件：i != nums[i] && nums[nums[i]] = nums[i]
 *
 * 输入：
 * [2, 3, 1, 0, 2, 5, 3]
 * 输出：2 或 3
 */
public class Main {
    public static void main(String[] args) {
        int result = findRepeatNumber(new int[]{2, 3, 1, 0, 2, 5, 3});
        System.out.println("重复元素 = " + result);
    }

    /**
     * 待遍历的数组nums
     * @param nums
     * @return
     *      重复数字
     */
    public static int findRepeatNumber(int[] nums) {
        if (nums.length < 2)
            return -1;

        int nlen = nums.length;
        int tmp = -1;
        // TODO 先对其数组进行原地排序
        for (int i = 0; i < nlen; i++) {
            while (i != nums[i]) {
                // TODO nums[i]和nums[nums[i]]进行交换
                if (nums[i] == nums[nums[i]]) {
                    return nums[i];
                }
                tmp = nums[i];
                nums[i] = nums[tmp];
                nums[tmp] = tmp;
            }
        }

        return -1;
    }
}
